#include <iostream>
#include <string>
#include <fstream>
#include <boost/dynamic_bitset.hpp>
#include <boost/lexical_cast.hpp>
#include <boost/algorithm/string.hpp>
#include <vector>

using namespace std;
using namespace boost;

const int buff = 256;
char line[buff];

struct edge {
    int node_a;
    int node_b;
    int c;
};

/**
 * Előkészíti a fájlt, ha van pre/postfix hozzáteszi és megnyitja
 */
string initialize_file(ifstream& fin, string filename, string prefix, string postfix)
{
    filename.insert( 0, prefix );
    if(postfix != "") {
        filename.replace( filename.end() - 4, filename.end(), postfix );
    }

    fin.open( filename.c_str() );

    if(fin.is_open()) {
        cout << "File opened successfully: " << filename << endl;
    } else {
        cout << "Unable to open: " << filename << endl;
        exit(0);
    }
    return filename;
}

/**
 * Beolvassa a gráfot
 */
void readgraph_bitset(string filename, vector<dynamic_bitset<> >& graph, int& nodes, int& edges)
{
    ifstream fin;
    initialize_file(fin, filename, "graphs/", "");

    while( fin.getline(line, buff) && line[0] != 'p' );     /** komment sorok **/
    int i = 0;
    string edgeline;

    /** A csúcsokat és az éleket az edgeline sorból olvasom ki
      * a split fgv segítségével, és elválasztónak a space karakter használom.
      * Ha több space karakter van a szavak között az megzavarja a split fgv-t,
      * ezért az ismétlődő space karaktereket törlöm előtte.
      */
    bool space_w = false;
    while(line[i] != '\0')
    {
        bool space_r = false;

        if(line[i] == ' ') {
            space_r = true;
        }

        if(space_r == true && space_w == false) {
            edgeline += " ";
            space_w = true;
        }

        if(line[i] != ' ') {
            edgeline += line[i];
            space_w = false;
        }
        ++i;
    }

    vector<string> fields;
    split(fields, edgeline, is_any_of(" ") );                      /** splitter: ' ' **/

    nodes = atoi(fields[2].c_str());                        /** nodes **/
    edges = atoi(fields[3].c_str());                        /** edges **/

    for(int i = 0; i < nodes; ++i) {                        /** gráf inicializálás **/
        dynamic_bitset<> tmp(nodes);
        graph.push_back(tmp);
    }

    string edge;                                            /** A gráf élei lesznek **/
    while( fin >> edge ) {
        if(edge == "e") {
            fin>>edge;
            int node_a = atoi( edge.c_str() );
            fin>>edge;
            int node_b = atoi( edge.c_str() );
            graph[node_a - 1][node_b - 1] = 1;
            graph[node_b - 1][node_a - 1] = 1;
        }
    }
    fin.close();
    cout<<"File has been loaded."<<endl<<endl;
}
/**
 * Beolvassa a színezés eredményét (col)
 */
void loadcolors(vector<dynamic_bitset<> >& colorclasses, string filename, int s, int nodes)
{
    ifstream fin;
    initialize_file(fin, filename, "cols/", "_" + lexical_cast<string>(s) + ".col");

    while( fin.getline(line, buff) && line[0] != 's' );

    string l( line );
    vector<string> fields;
    split(fields, l, is_any_of(" ") );

    int colors = atoi(fields[2].c_str());

    for(int i = 0; i < colors; ++i) {
        dynamic_bitset<> temp(nodes);
        colorclasses.push_back(temp);
    }

    string label;
    while( fin >> label ) {
        if(label == "l") {
            fin>>label;
            int node = atoi( label.c_str() );
            fin>>label;
            int cr = atoi( label.c_str() );
            colorclasses[cr - 1][node - 1] = 1;
        }
    }
    fin.close();
    cout<<"File has been loaded."<<endl;
}

/**
 * Beolvassa a checkpoint fájlt:
 * Tartalma:
 *      A kvázi színosztályok.
 *      Az eliminálandó élek.
 *      A már eliminált élek.
 */
string loadcheckpoint(vector<dynamic_bitset<> >& colorclasses, vector<pair<int, int> >& edges_to_delete,
                      vector<pair<int, int> >& deleted_edges, string filename, int s, int nodes, int k)
{
    ifstream fin;
    string checkpoint_file = initialize_file(fin, filename, "checkpoints/", ".chk");

    while( fin.getline(line, buff) && line[0] != 's' );

    string l( line );
    vector<string> fields;
    split(fields, l, is_any_of(" ") );

    int colors = atoi(fields[2].c_str());

    for(int i = 0; i < colors; ++i) {
        dynamic_bitset<> temp(nodes);
        colorclasses.push_back(temp);
    }

    string label;
    while( fin >> label ) {                         /** Kvázi színosztályok. **/
        if(label == "l") {
            fin>>label;
            int node = atoi( label.c_str() );
            fin>>label;
            int cr = atoi( label.c_str() );
            colorclasses[cr - 1][node - 1] = 1;
        } else if(label == "c") {
            break;
        }
    }

    while( fin >> label ) {                         /** Eliminálandó élek. **/
        if(label == "e") {
            fin>>label;
            int node_a = atoi( label.c_str() );
            fin>>label;
            int node_b = atoi( label.c_str() );
            edges_to_delete.push_back( make_pair(node_a - 1, node_b - 1) );
        } else if(label == "c") {
            break;
        }
    }
    fin.getline(line, buff);

    while( fin >> label ) {                         /** Már eliminált élek. **/
        if(label == "e") {
            fin>>label;
            int node_a = atoi( label.c_str() );
            fin>>label;
            int node_b = atoi( label.c_str() );
            deleted_edges.push_back( make_pair(node_a - 1, node_b - 1) );
        }
    }
    fin.close();
    cout<<"File has been loaded."<<endl;
    return checkpoint_file;
}

/**
 * Lementi a színezés eredményét.
 */
void savecolors(vector<dynamic_bitset<> > graph, vector<dynamic_bitset<> > colorclasses, string filename, int s)
{
    string s_string = lexical_cast<string>(s);
    filename.replace( filename.end() - 4, filename.end(), "_" + s_string + ".col" );
    filename.insert( 0, "cols/" );
    ofstream fout( filename.c_str() );
    fout<<"c "<<s<<"-free coloring of"<<endl;
    fout<<"c "<<filename.substr(0, filename.size()-4)<<endl;
    fout<<"c nodes "<<graph.size()<<endl;
    fout<<"s col "<<colorclasses.size()<<endl;
    for(int i = 0; i < graph.size(); ++i) {
        for(int j = 0; j < colorclasses.size(); ++j) {
            if(colorclasses[j][i]) {
                fout<<"l "<<i + 1<<" "<<j + 1<<endl;
            }
        }
    }
    fout.close();
}

/**
 * A distr.cpp használja, lementi a párhuzamos számára az első checkpointot.
 * Tartalma:
 *      Kvázi színosztályok.
 *      Eliminálandó élek.
 * A már eliminált éleket a párhuzamos program írja, minden megvizsgált él után.
 */
void save_checkpoint(vector<dynamic_bitset<> > graph, vector<dynamic_bitset<> > colorclasses, string filename, int s, int k, vector<edge> edge_set)
{
    string s_string = lexical_cast<string>(s);
    string k_string = lexical_cast<string>(k);
    filename.replace( filename.end() - 4, filename.end(), "_" + s_string + "_" + k_string + ".chk" );
    filename.insert( 0, "checkpoints/" );
    ofstream fout( filename.c_str() );

    fout<<"c "<<s<<"-free coloring of"<<endl;
    fout<<"c "<<filename.substr(0, filename.size()-4)<<endl;
    fout<<"c nodes "<<graph.size()<<endl;
    fout<<"s col "<<colorclasses.size()<<endl;

    for(int i = 0; i < graph.size(); ++i) {
        for(int j = 0; j < colorclasses.size(); ++j) {
            if(colorclasses[j][i]) {
                fout<<"l "<<i + 1<<" "<<j + 1<<endl;
            }
        }
    }

    fout<<endl<<"c  edges_to_delete"<<endl<<endl;;
    for(int i = 0; i < edge_set.size(); ++i) {
        fout<<"e "<<edge_set[i].node_a + 1<<" "<<edge_set[i].node_b + 1<<endl;
    }
    fout<<endl<<"c Deleted edges e node1 node2"<<endl<<endl;
    fout.close();
}

/**
 * Kiírja a gráfot a képernyőre
 */
ostream& operator<<(ostream& os, vector<boost::dynamic_bitset<> > graph)
{
    int size0 = graph.size();
    os << "Nodes: " << size0 << endl;
    for(int i=0; i < size0; ++i) {
        for(int j=0; j < size0; ++j) {
            os << graph[i][j] << ' ';
        }
        os<<endl;
    }
    return os;
}

void printsize(int nodes, int edges)
{
    cout << "Nodes: " << nodes << endl << "Edges: " << edges << endl;
}

void printsize_to_file(string filename, int edges, int colors, int nodes)
{
    ofstream fout;
    fout.open( filename.c_str(), ios::out | ios::app );
    fout << endl;
    fout  << nodes << '\t' << edges << '\t' << colors;
    fout.close();
}

void printgraph_to_pbm(vector<boost::dynamic_bitset<> > graph, string filename, int s)
{
    int size0 = graph.size();
    string s_string = lexical_cast<string>(s);
    filename.replace( filename.end() - 4, filename.end(),  "_" + s_string + ".pbm" );
    filename.insert( 0, "pbms/" );

    ofstream fout( filename.c_str() );
    fout << "P1" << endl << "# " << filename << endl << size0 << ' ' << size0 << endl;
    for(int i = 0; i < size0; ++i) {
        for(int j = 0; j < size0; ++j) {
            fout << graph[i][j] << ' ';
        }
        fout<<endl;
    }
}
